#include <iostream>
#include <vector>
#include <functional>
using namespace std;

function<void(vector<int> &)> output = [](vector<int> &arr) -> void
{
    int length = arr.size();
    for (int i = 0; i < length; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
};

void selectSort_1(vector<int> &arr)
{
    int length = arr.size();
    for (int i = 0; i < length - 1; ++i)
    {
        int minIndex = i;
        for (int j = i + 1; j < length; ++j)
        {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        if (minIndex == i)
            continue;
        arr[i] = arr[i] ^ arr[minIndex];
        arr[minIndex] = arr[i] ^ arr[minIndex];
        arr[i] = arr[i] ^ arr[minIndex];
    }
}

void selectSort_2(vector<int> &arr)
{
    int length = arr.size();
    for (int i = 0; i < length / 2; ++i)
    {
        int minIndex = i;
        int maxIndex = i;
        for (int j = i + 1; j < length - i; ++j)
        {
            if (arr[minIndex] > arr[j])
                minIndex = j;
            if (arr[maxIndex] < arr[j])
                maxIndex = j;
        }
        if (minIndex == maxIndex)
            break;
        if (minIndex != i)
        {
            arr[minIndex] = arr[i] - arr[minIndex];
            arr[i] = arr[i] - arr[minIndex];
            arr[minIndex] = arr[i] + arr[minIndex];
        }
        if (maxIndex == i)
            maxIndex = minIndex;
        int lastIndex = length - 1 - i;
        if (lastIndex != maxIndex)
        {
            arr[lastIndex] = arr[maxIndex] - arr[lastIndex];
            arr[maxIndex] = arr[maxIndex] - arr[lastIndex];
            arr[lastIndex] = arr[maxIndex] + arr[lastIndex];
        }
    }
}

int main()
{
    vector<int> arr = {6, 2, 1, 3, 5, 4};

    vector<int> temp(arr);
    output(temp);
    selectSort_1(temp);
    output(temp);
    temp = arr;
    output(temp);
    selectSort_2(temp);
    output(temp);
    return 0;
}
